package bintree.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: yuisama
 * @Date: 2021/9/7 12:09
 * @Description:判断一棵树是否是平衡二叉树
 * https://leetcode-cn.com/problems/balanced-binary-tree/
 */
public class Num110_IsBalancedTree {
    // 用Map保存已经计算过的节点以及其深度，避免重复递归运算
    Map<TreeNode,Integer> map = new HashMap<>();
    public boolean isBalanced(TreeNode root) {
        // 若空树一定平衡
        if (root == null)
            return true;
        // 当前树是否平衡
        int leftMaxDep;
        int rightMaxDep;
        if (map.containsKey(root.left)) {
            leftMaxDep = map.get(root.left);
        }else {
            leftMaxDep = maxDepth(root.left);
            map.put(root.left,leftMaxDep);
        }
        if (map.containsKey(root.right)) {
            rightMaxDep = map.get(root.right);
        }else {
            rightMaxDep = maxDepth(root.right);
            map.put(root.right,rightMaxDep);
        }
        if (Math.abs(leftMaxDep - rightMaxDep) > 1) {
            return false;
        }
        // 递归判断左树和右树是否平衡
        return isBalanced(root.left) && isBalanced(root.right);
    }

    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}
